package com.cat.dataStructure02;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-flowers-in-full-bloom/
 * @create 2025/10/23 23:31
 * @since JDK17
 */

public class Solution55 {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        Map<Integer, Integer> map = new HashMap<>();
        for (var f : flowers) {
            map.merge(f[0], 1, Integer::sum);
            map.merge(f[1] + 1, -1, Integer::sum);
        }
        List<Integer> keys = new ArrayList<Integer>(map.keySet());
        Collections.sort(keys);
        int n = keys.size(), m = people.length;
        int[][] p = new int[m][2];
        for (int i = 0; i < m; i++) {
            p[i] = new int[] { people[i], i };
        }
        Arrays.sort(p, (a, b) -> a[0] - b[0]);
        int[] ans = new int[m];
        for (int i = 0, j = 0, sum = 0; i < m; i++) {
            while (j < n && keys.get(j) <= p[i][0]) {
                sum += map.get(keys.get(j++));
            }
            ans[p[i][1]] = sum;
        }

        return ans;
    }
}
